package com.zy.algorithm.v2;

import com.zy.algorithm.v2.bean.BucketSimpleNode;
import com.zy.algorithm.v2.bean.SimpleNode;
import com.zy.utils.DataBuildUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BucketSortUtils {

    public static void bucketSort(List<BucketSimpleNode> stepList, int[] sort) {
        int n = sort.length;
        int mn = sort[0], mx = sort[0];
        // 找出数组中的最大最小值
        for (int i = 1; i < n; i++) {
            mn = Math.min(mn, sort[i]);
            mx = Math.max(mx, sort[i]);

            BucketSimpleNode bucketSimpleNode = new BucketSimpleNode(mx, mn);
            bucketSimpleNode.setStepEnd(Arrays.copyOf(sort, sort.length));
            bucketSimpleNode.addOpIndex(i);
            bucketSimpleNode.setDes("大小:" + sort.length + " 最小值:" + mn + " 最大值:" + mx);
            stepList.add(bucketSimpleNode);
        }

        int size = (mx - mn) / n + 1; // 每个桶存储数的范围大小，使得数尽量均匀地分布在各个桶中，保证最少存储一个
        int cnt = (mx - mn) / size + 1; // 桶的个数，保证桶的个数至少为1

        System.out.println("mn:" + mn + " mx:" + mx + " (mx - mn)=" + (mx - mn));
        System.out.println("size:" + size + " cnt:" + cnt);

        BucketSimpleNode bucketSimpleNode = new BucketSimpleNode(mx, mn);
        bucketSimpleNode.addSortedIndex(0);
        bucketSimpleNode.setStepEnd(Arrays.copyOf(sort, sort.length));
        bucketSimpleNode.setDes("大小:" + sort.length + " 最小值:" + mn + " 最大值:" + mx + " 桶个数:" + cnt + " 桶范围:" + size);
        stepList.add(bucketSimpleNode);

        List<Integer>[] buckets = new ArrayList[cnt]; // 声明cnt个桶
        for (int i = 0; i < cnt; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 扫描一遍数组，将数放进桶里
        //分桶

        for (int i = 0; i < n; i++) {
            int idx = (sort[i] - mn) / size;  //取整数-表示在哪一个桶
            buckets[idx].add(sort[i]);  //插入该数据


            bucketSimpleNode = new BucketSimpleNode(mx, mn);
            bucketSimpleNode.addOpIndex(i);
            bucketSimpleNode.setStepEnd(Arrays.copyOf(sort, sort.length));
            bucketSimpleNode.setSortedS(buckets);
            bucketSimpleNode.setDes("大小:" + sort.length + " 最小值:" + mn + " 最大值:" + mx + " 桶个数:" + cnt + " 桶范围:" + size);
            stepList.add(bucketSimpleNode);
        }
        // 对各个桶中的数进行排序，这里用库函数快速排序
        //桶内排序
        int baseIndex = 0;
        for (int i = 0; i < cnt; i++) {
            // 默认是按从小打到排序
            List<Integer> bucket = buckets[i];


            List<SimpleNode> list = SortUtilsV2.insertionSort(bucket);
            for (SimpleNode simpleNode : list) {

                buckets[i] = simpleNode.getStepStartList();
                List<Integer> opIndexList = simpleNode.getOpIndex();
                List<Integer> newOpIndexList = simpleNode.getOpIndex();
                for (Integer integer : opIndexList) {
                    newOpIndexList.add(integer + baseIndex);
                }


                bucketSimpleNode = new BucketSimpleNode(mx, mn);
                bucketSimpleNode.addOpIndex(i);
                bucketSimpleNode.setStepEnd(Arrays.copyOf(sort, sort.length));
                bucketSimpleNode.setSortedS(buckets);
                bucketSimpleNode.setSortedIndex(newOpIndexList);
                bucketSimpleNode.setDes("大小:" + sort.length + " 最小值:" + mn + " 最大值:" + mx + " 桶个数:" + cnt + " 桶范围:" + size);
                stepList.add(bucketSimpleNode);
            }


            baseIndex += bucket.size();
        }

        // 依次将各个桶中的数据放入返回数组中
        // 合并
        System.out.println(Arrays.toString(buckets));

        int index = 0;
        for (int i = 0; i < cnt; i++) {
            for (int j = 0; j < buckets[i].size(); j++) {
                sort[index++] = buckets[i].get(j);
            }
        }
    }


    //桶-临时合并


    public static List<BucketSimpleNode> bucketSort(int size, int range) {
        int[] array = DataBuildUtils.getRandomSortArray(size, range);
        List<BucketSimpleNode> stepList = new ArrayList<>();

        bucketSort(stepList, array);
        return stepList;
    }
}

